
package main

import "fmt"

const MOD = 10000007

func solution(n int, A int, B int, arrayA []int) int {
	if A > 9 || B > 9 {
		panic("A and B must be <= 9")
	}
	if n != len(arrayA) {
		panic("n must equal length of arrayA")
	}

	dp := make([][]int, n+1)
	for i := range dp {
		dp[i] = make([]int, 10)
	}

	sumValue := 0
	for _, num := range arrayA {
		sumValue = (sumValue + num) % 10
	}
	ret := (A + B) % 10
	res := 0

	if sumValue == B {
		res++
	}

	dp[0][0] = 1
	if sumValue == ret {
		for i := 1; i <= n; i++ {
			for j := 0; j < 10; j++ {
				prev := (j - arrayA[i-1]) % 10
				if prev < 0 {
					prev += 10
				}
				dp[i][j] = (dp[i-1][j] + dp[i-1][prev]) % MOD
			}
		}
		return (dp[n][A] + res) % MOD
	} else {
		if sumValue == A {
			res++
		}
		return res
	}
}

func main() {
	fmt.Println(solution(3, 1, 2, []int{1,1,1}) == 3)
	fmt.Println(solution(3, 3, 5, []int{1,1,1}) == 1)
	fmt.Println(solution(2, 1, 1, []int{1,1}) == 2)
}
